{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Lemonade Change"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: lemonadeChange"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #柠檬水找零"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>在柠檬水摊上，每一杯柠檬水的售价为&nbsp;<code>5</code>&nbsp;美元。顾客排队购买你的产品，（按账单 <code>bills</code> 支付的顺序）一次购买一杯。</p>\n",
    "\n",
    "<p>每位顾客只买一杯柠檬水，然后向你付 <code>5</code> 美元、<code>10</code> 美元或 <code>20</code> 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 <code>5</code> 美元。</p>\n",
    "\n",
    "<p>注意，一开始你手头没有任何零钱。</p>\n",
    "\n",
    "<p>给你一个整数数组 <code>bills</code> ，其中 <code>bills[i]</code> 是第 <code>i</code> 位顾客付的账。如果你能给每位顾客正确找零，返回&nbsp;<code>true</code>&nbsp;，否则返回 <code>false</code>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>bills = [5,5,5,10,20]\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：\n",
    "</strong>前 3 位顾客那里，我们按顺序收取 3 张 5 美元的钞票。\n",
    "第 4 位顾客那里，我们收取一张 10 美元的钞票，并返还 5 美元。\n",
    "第 5 位顾客那里，我们找还一张 10 美元的钞票和一张 5 美元的钞票。\n",
    "由于所有客户都得到了正确的找零，所以我们输出 true。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>bills = [5,5,10,10,20]\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>\n",
    "前 2 位顾客那里，我们按顺序收取 2 张 5 美元的钞票。\n",
    "对于接下来的 2 位顾客，我们收取一张 10 美元的钞票，然后返还 5 美元。\n",
    "对于最后一位顾客，我们无法退回 15 美元，因为我们现在只有两张 10 美元的钞票。\n",
    "由于不是每位顾客都得到了正确的找零，所以答案是 false。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= bills.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>bills[i]</code>&nbsp;不是&nbsp;<code>5</code>&nbsp;就是&nbsp;<code>10</code>&nbsp;或是&nbsp;<code>20</code>&nbsp;</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [lemonade-change](https://leetcode.cn/problems/lemonade-change/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [lemonade-change](https://leetcode.cn/problems/lemonade-change/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[5,5,5,10,20]', '[5,5,10,10,20]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def test(self):\n",
    "        list1 = [1,2,4,3,2,1,9]\n",
    "        #list1.sort()\n",
    "        #list1.reverse()\n",
    "        #del list1[1]\n",
    "        print(list1)\n",
    "        #return list1\n",
    "    \n",
    "    def lemonadeChange(self, bills: List[int]) -> bool:\n",
    "        #self.test()\n",
    "        changes = []\n",
    "        for i in range(len(bills)):\n",
    "            bill = bills[i]\n",
    "            if bill < 5 or bill % 5 != 0:\n",
    "                print(\"bill error!\")\n",
    "                return False\n",
    "            if bill == 5:\n",
    "                changes.append(5)\n",
    "            else:\n",
    "                changes.sort()\n",
    "                changes.reverse()\n",
    "                #delet = []\n",
    "                for j in range(len(changes)):\n",
    "                    change = changes[j]\n",
    "                    if change < bill:\n",
    "                        bill -= change\n",
    "                        changes[j] = 0 #delet.append(j) #del changes[j]\n",
    "                if bill > 5:\n",
    "                    return False\n",
    "                else:\n",
    "                    #for num in delet:\n",
    "                    #    changes[num] = 0    #del changes[num]\n",
    "                    changes.append(bills[i])\n",
    "        return True\n",
    "\n",
    "            \n",
    "            #    changes.sort(reverse)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lemonadeChange(self, bills: List[int]) -> bool:\n",
    "        log = [0,0,0]\n",
    "        for i in range(len(bills)):\n",
    "            if bills[i] == 5:\n",
    "                log[0] += 1\n",
    "            elif bills[i] == 10:\n",
    "                if log[0] >= 1:\n",
    "                    log[0] -= 1\n",
    "                    log[1] += 1\n",
    "                else:\n",
    "                    return False\n",
    "            elif bills[i] == 20:\n",
    "                if log[1] >= 1 and log[0]>=1:\n",
    "                    log[0] -= 1\n",
    "                    log[1] -= 1\n",
    "                    log[2] += 1\n",
    "                elif log[0]>=3:\n",
    "                    log[0] -= 3\n",
    "                    log[2] += 1\n",
    "                else:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lemonadeChange(self, bills: List[int]) -> bool:\n",
    "        money = {5:0,10:0,20:0}\n",
    "        for i in bills:\n",
    "            money[i] += 1\n",
    "            if i == 10 :\n",
    "                if money[5]>=1:\n",
    "                    money[5] -= 1\n",
    "                else:return(False)\n",
    "            if i == 20:\n",
    "                if money[10]>=1:\n",
    "                    if money[5]>=1:\n",
    "                        money[10] -= 1\n",
    "                        money[5] -= 1\n",
    "                    else:return(False)\n",
    "                else:\n",
    "                    if money[5]>=3:\n",
    "                        money[5] -= 3\n",
    "                    else:return(False)\n",
    "        return(True)\n",
    "\n",
    "\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lemonadeChange(self, bills: List[int]) -> bool:\n",
    "        changes = [0, 0]\n",
    "        for i in range(len(bills)):\n",
    "            if bills[i] == 5:\n",
    "                changes[0] += 1\n",
    "            elif bills[i] == 10:\n",
    "                if changes[0] == 0:\n",
    "                    return False\n",
    "                else:\n",
    "                    changes[0] -= 1\n",
    "                    changes[1] += 1\n",
    "            else:\n",
    "                if changes[1] > 0:\n",
    "                    changes[1] -=1\n",
    "                    if changes[0] > 0:\n",
    "                        changes[0] -= 1\n",
    "                    else:\n",
    "                        return False\n",
    "                else:\n",
    "                    if changes[0] < 3:\n",
    "                        return False\n",
    "                    else: changes[0] -= 3\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lemonadeChange(self, bills: List[int]) -> bool:\n",
    "        five = 0\n",
    "        ten = 0\n",
    "        for ch in bills:\n",
    "            if ch == 5:\n",
    "                five += 1\n",
    "            elif ch == 10:\n",
    "                if five > 0:\n",
    "                    five -= 1\n",
    "                    ten += 1\n",
    "                else:\n",
    "                    return False\n",
    "            else:\n",
    "                if (ten > 0 and five > 0):\n",
    "                    ten -= 1\n",
    "                    five -= 1\n",
    "                elif five >= 3:\n",
    "                    five -= 3\n",
    "                else:\n",
    "                    return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lemonadeChange(self, bills: List[int]) -> bool:\n",
    "        five = 0\n",
    "        ten = 0\n",
    "        for bill in bills:\n",
    "            if bill == 5:\n",
    "                five += 1\n",
    "            if bill == 10:\n",
    "                if five > 0:\n",
    "                    five -= 1\n",
    "                    ten += 1\n",
    "                else:\n",
    "                    return False\n",
    "            if bill == 20:                \n",
    "                if ten > 0 and five > 0:\n",
    "                    ten -= 1\n",
    "                    five -= 1\n",
    "                elif five >= 3:\n",
    "                    five -= 3\n",
    "                else:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lemonadeChange(self, bills: List[int]) -> bool:\n",
    "        my_money = {5:0,10:0,20:0}\n",
    "        for index, bill in enumerate(bills) :\n",
    "            if bill == 5:\n",
    "                my_money[5] += 1\n",
    "            if bill == 10:\n",
    "                my_money[10] += 1\n",
    "                my_money[5] -= 1\n",
    "            if bill == 20:\n",
    "                my_money[20] += 1\n",
    "                if my_money[10] == 0:\n",
    "                    my_money[5] -= 3\n",
    "                else:\n",
    "                    my_money[5] -=1\n",
    "                    my_money[10] -=1\n",
    "            if my_money[5] < 0 or my_money[10] < 0:\n",
    "                print(index)\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lemonadeChange(self, bills: List[int]) -> bool:\n",
    "        hash = {5:0,10:0,20:0}\n",
    "        for i in bills:\n",
    "            if i == 5:\n",
    "                hash[i] += 1\n",
    "            elif i == 10:\n",
    "                if hash[5] > 0:\n",
    "                    hash[i] += 1\n",
    "                    hash[5] -= 1\n",
    "                else:\n",
    "                    return False\n",
    "            else:\n",
    "                if hash[10] > 0 and hash[5] > 0:\n",
    "                    hash[i] += 1\n",
    "                    hash[10] -= 1\n",
    "                    hash[5] -= 1\n",
    "                elif hash[5] >= 3:\n",
    "                    hash[i] += 1\n",
    "                    hash[5] -= 3\n",
    "                else:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lemonadeChange(self, bills: List[int]) -> bool:\n",
    "        hash = {5:0,10:0,20:0}\n",
    "        for i in bills:\n",
    "            if i == 5:\n",
    "                hash[i] = hash.get(i, 0) + 1\n",
    "            elif i == 10:\n",
    "                if hash[5] > 0:\n",
    "                    hash[i] = hash.get(i, 0) + 1\n",
    "                    hash[5] -= 1\n",
    "                else:\n",
    "                    return False\n",
    "            else:\n",
    "                if hash[10] > 0 and hash[5] > 0:\n",
    "                    hash[i] = hash.get(i, 0) + 1\n",
    "                    hash[10] -= 1\n",
    "                    hash[5] -= 1\n",
    "                elif hash[5] >= 3:\n",
    "                    hash[i] = hash.get(i, 0) + 1\n",
    "                    hash[5] -= 3\n",
    "                else:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lemonadeChange(self, bills: List[int]) -> bool:\n",
    "        five = 0\n",
    "        ten = 0\n",
    "\n",
    "        for b in bills:\n",
    "            if b == 5:\n",
    "                five += 1\n",
    "                continue\n",
    "\n",
    "            elif b == 10:\n",
    "                if five > 0:\n",
    "                    five -= 1\n",
    "                    ten += 1\n",
    "                    continue\n",
    "                else:\n",
    "                    return False\n",
    "            elif b == 20:\n",
    "                if ten > 0 and five > 0:\n",
    "                    ten -= 1\n",
    "                    five -= 1\n",
    "                    continue\n",
    "                elif five >= 3:\n",
    "                    five -= 3\n",
    "                    continue\n",
    "                else:\n",
    "                    return False\n",
    "        return True\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lemonadeChange(self, bills: List[int]) -> bool:\n",
    "        numOf5 = 0\n",
    "        numOf10 = 0\n",
    "        numOf20 = 0\n",
    "\n",
    "        for i in range(len(bills)):\n",
    "            if bills[i] == 5:\n",
    "                numOf5 += 1\n",
    "            elif bills[i] == 10:\n",
    "                numOf5 -= 1\n",
    "                numOf10 += 1\n",
    "            elif bills[i] == 20:\n",
    "                if numOf10 > 0:\n",
    "                    numOf10 -= 1\n",
    "                    numOf5 -= 1\n",
    "                else:\n",
    "                    numOf5 -= 3\n",
    "            if numOf5 < 0:\n",
    "                return False\n",
    "        \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def lemonadeChange(self, bills: List[int]) -> bool:\n",
    "        wallet = defaultdict(int)\n",
    "        moneys = [10, 5]\n",
    "        n = len(moneys)\n",
    "\n",
    "        for bill in bills:\n",
    "            wallet[bill] += 1\n",
    "            res = bill - 5\n",
    "\n",
    "            i = 0\n",
    "            while res and i < n:\n",
    "                money = moneys[i]\n",
    "                num = min(res // money, wallet[money])\n",
    "                wallet[money] -= num\n",
    "                res -= money * num\n",
    "                i += 1\n",
    "            \n",
    "            if res:\n",
    "                return False\n",
    "        \n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lemonadeChange(self, bills: List[int]) -> bool:\n",
    "        left = {5:0, 10:0}\n",
    "        if bills[0] != 20:\n",
    "            left[bills[0]] += 1\n",
    "        for i in range(1,len(bills)):\n",
    "            change = bills[i] - 5\n",
    "            if change == 0:\n",
    "                left[5] += 1\n",
    "            elif change == 5:\n",
    "                if left[5] >= 1:\n",
    "                    left[5] -= 1\n",
    "                    left[10] += 1\n",
    "                else:\n",
    "                    return False\n",
    "            else:\n",
    "                if left[10] >= 1 and left[5] >=1:\n",
    "                    left[10] -= 1\n",
    "                    left[5] -= 1\n",
    "                elif left[5] >= 3:\n",
    "                    left[5] -= 3\n",
    "                else:\n",
    "                    return False\n",
    "        return True\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lemonadeChange(self, bills: List[int]) -> bool:\n",
    "        five,ten=0,0\n",
    "        for bill in bills:\n",
    "            if bill==5:\n",
    "                five+=1\n",
    "            elif bill==10:\n",
    "                if five<1: return False\n",
    "                five-=1\n",
    "                ten+=1\n",
    "            else:\n",
    "                if ten>0 and five>0:\n",
    "                    ten-=1\n",
    "                    five-=1\n",
    "                elif five>2:\n",
    "                    five-=3\n",
    "                else:\n",
    "                    return False\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lemonadeChange(self, bills: List[int]) -> bool:\n",
    "        seen = {5: 0, 10: 0}\n",
    "        for ch in bills:\n",
    "            if ch == 5:\n",
    "                seen[ch] += 1\n",
    "            elif ch == 10:\n",
    "                if seen[5] > 0:\n",
    "                    seen[5] -= 1\n",
    "                    seen[10] += 1\n",
    "                else:\n",
    "                    return False\n",
    "            else:\n",
    "                if (seen[10] >= 1 and seen[5] >= 1):\n",
    "                    seen[10] -= 1\n",
    "                    seen[5] -= 1\n",
    "                elif seen[5] >= 3:\n",
    "                    seen[5] -= 3\n",
    "                else:\n",
    "                    return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def lemonadeChange(self, bills: List[int]) -> bool:\r\n",
    "        wallet = {5:0, 10:0, 20:0}\r\n",
    "        for m in bills:\r\n",
    "            wallet[m] += 1\r\n",
    "            if m == 10:\r\n",
    "                wallet[5] -= 1\r\n",
    "            if m == 20:\r\n",
    "                if wallet[10] > 0:\r\n",
    "                    wallet[10] -= 1\r\n",
    "                    wallet[5] -= 1\r\n",
    "                else:\r\n",
    "                    wallet[5] -= 3\r\n",
    "            if wallet[5] < 0 or wallet[10] < 0:\r\n",
    "                return False\r\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lemonadeChange(self, bills: List[int]) -> bool:\n",
    "        five = 0\n",
    "        ten = 0\n",
    "        for bill in bills:\n",
    "            if bill == 5:\n",
    "                five += 1\n",
    "            elif bill == 10:\n",
    "                if five == 0:\n",
    "                    return False\n",
    "                five -= 1\n",
    "                ten += 1\n",
    "            else:\n",
    "                if ten > 0 and five > 0:\n",
    "                    ten -= 1\n",
    "                    five -= 1\n",
    "                elif five > 2:\n",
    "                    five -= 3\n",
    "                else:\n",
    "                    return False\n",
    "        \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lemonadeChange(self, bills: List[int]) -> bool:\n",
    "        hash = {5:0,10:0,20:0}\n",
    "        for i in bills:\n",
    "            if i == 5:\n",
    "                hash[i] += 1\n",
    "            elif i == 10:\n",
    "                if hash[5] > 0:\n",
    "                    hash[i] += 1\n",
    "                    hash[5] -= 1\n",
    "                else:\n",
    "                    return False\n",
    "            else:\n",
    "                if hash[10] > 0 and hash[5] > 0:\n",
    "                    hash[i] += 1\n",
    "                    hash[10] -= 1\n",
    "                    hash[5] -= 1\n",
    "                elif hash[5] >= 3:\n",
    "                    hash[i] += 1\n",
    "                    hash[5] -= 3\n",
    "                else:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lemonadeChange(self, bills: List[int]) -> bool:\n",
    "        n=len(bills)\n",
    "        mycount = [0,0,0]\n",
    "        i=0\n",
    "        while i < n :\n",
    "            if bills[i]==5 :\n",
    "                mycount[0]+=1\n",
    "            elif bills[i]==10:\n",
    "                if mycount[0]>0:\n",
    "                    mycount[0]-=1\n",
    "                    mycount[1]+=1\n",
    "                else:\n",
    "                    return False\n",
    "            elif bills[i]==20:\n",
    "                if mycount[1]>0 and mycount[0]>0:\n",
    "                    mycount[0]-=1\n",
    "                    mycount[1]-=1\n",
    "                elif mycount[0]>=3:\n",
    "                    mycount[0]-=3\n",
    "                else:\n",
    "                    return False                    \n",
    "                \n",
    "            # mycount+=5\n",
    "            i+=1\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lemonadeChange(self, bills: List[int]) -> bool:\n",
    "        change = [0, 0, 0] # 20 10 5\n",
    "        for i in bills:\n",
    "            if i == 5:\n",
    "                change[2] += 1\n",
    "            elif i == 10:\n",
    "                if change[2] < 1:\n",
    "                    return False\n",
    "                change[1] += 1\n",
    "                change[2] -= 1\n",
    "            elif i == 20:\n",
    "                if change[1] > 0 and change[2] > 0:\n",
    "                    change[1] -= 1\n",
    "                    change[2] -= 1\n",
    "                elif change[2] >= 3:\n",
    "                    change[2] -= 3\n",
    "                else:\n",
    "                    return False\n",
    "                change[0] += 1\n",
    "        return True\n",
    "\n",
    "                    \n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lemonadeChange(self, bills: List[int]) -> bool:\n",
    "        # bills = [5,5,5,20,5,5,5,20,5,5,5,10,5,20,10,20,10,20,5,5]\n",
    "        # bills.sort()\n",
    "        # print(bills)\n",
    "        save = 0\n",
    "        ten = 0\n",
    "        for idx,b in enumerate(bills):\n",
    "            print(b,save,ten)\n",
    "            if b == 5:\n",
    "                save += 1\n",
    "            elif b == 10:\n",
    "                if save < 1:\n",
    "                    return False\n",
    "                save -= 1\n",
    "                ten += 1\n",
    "            else:\n",
    "                if save >= 1 and ten >= 1: # 1-5 1-10\n",
    "                    save -= 1\n",
    "                    ten -= 1\n",
    "                elif save >= 3: # 3张五块的\n",
    "                    save -= 3\n",
    "                else:\n",
    "                    return False\n",
    "            \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lemonadeChange(self, bills: List[int]) -> bool:\n",
    "        five = ten =0\n",
    "        for i in bills:\n",
    "            if i == 5:\n",
    "                five +=1\n",
    "            elif i == 10:\n",
    "                if five < 1: return False\n",
    "                five -=1\n",
    "                ten +=1\n",
    "            else:\n",
    "                if five >0 and ten >0:\n",
    "                    five -=1\n",
    "                    ten -=1\n",
    "                elif five>2:\n",
    "                    five -=3\n",
    "                else:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lemonadeChange(self, bills: List[int]) -> bool:\n",
    "        mybills = []\n",
    "        money = bills\n",
    "        for i in range(len(bills)):\n",
    "            if bills[i] == 5:\n",
    "                mybills.append(5)\n",
    "            elif bills[i] == 10:\n",
    "                if 5 not in mybills:\n",
    "                    return False\n",
    "                else:\n",
    "                    mybills.remove(5)\n",
    "                    mybills.append(10)\n",
    "            elif bills[i] == 20:\n",
    "                a = mybills.count(5)\n",
    "                if (10 in mybills) and (5 in mybills):\n",
    "                    mybills.remove(5)\n",
    "                    mybills.remove(10)\n",
    "                    mybills.append(20)\n",
    "                elif a >= 3:\n",
    "                    mybills.remove(5)\n",
    "                    mybills.remove(5)\n",
    "                    mybills.remove(5)\n",
    "                    mybills.append(20)\n",
    "                else:\n",
    "                    return False\n",
    "        return True\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lemonadeChange(self, bills: List[int]) -> bool:\n",
    "        sum_ = []\n",
    "        for i in range(len(bills)):\n",
    "            if bills[i] == 5:\n",
    "                sum_.append(5)\n",
    "            elif bills[i] == 10:\n",
    "                if 5 in sum_:\n",
    "                    sum_.remove(5)\n",
    "                    sum_.append(10)\n",
    "                else:\n",
    "                    return False\n",
    "            else:\n",
    "                if 5 in sum_ and 10 in sum_:\n",
    "                    sum_.remove(5)\n",
    "                    sum_.remove(10)\n",
    "                    sum_.append(20)\n",
    "                elif sum_.count(5)>=3:\n",
    "                    sum_.remove(5)\n",
    "                    sum_.remove(5)\n",
    "                    sum_.remove(5)\n",
    "                    sum_.append(20)\n",
    "                else:\n",
    "                    return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def lemonadeChange(self, bills: List[int]) -> bool:\r\n",
    "        can = []\r\n",
    "\r\n",
    "        for b in bills:\r\n",
    "            if b == 5: can.append(b)\r\n",
    "            if b == 10:\r\n",
    "                if 5 in can:\r\n",
    "                    can.remove(5)\r\n",
    "                    can.append(b)\r\n",
    "                else:\r\n",
    "                    return False\r\n",
    "            if b == 20:\r\n",
    "                if 10 in can and 5 in can:\r\n",
    "                    can.remove(5)\r\n",
    "                    can.remove(10)\r\n",
    "                else:\r\n",
    "                    if can.count(5) >= 3:\r\n",
    "                        can.remove(5)\r\n",
    "                        can.remove(5)\r\n",
    "                        can.remove(5)                        \r\n",
    "                    else:\r\n",
    "                        return False \r\n",
    "                can.append(20)      \r\n",
    "        return True\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lemonadeChange(self, bills: List[int]) -> bool:\n",
    "        wallet = [0,0,0]\n",
    "        for i in bills:\n",
    "            if i == 5:\n",
    "                wallet[0] += 1\n",
    "            if i == 10:\n",
    "                wallet[1] += 1\n",
    "                wallet[0] -= 1\n",
    "            if i == 20:\n",
    "                wallet[2] += 1\n",
    "                if wallet[1]>0 and wallet[0]>0:\n",
    "                    wallet[1] -= 1\n",
    "                    wallet[0] -= 1\n",
    "                    continue\n",
    "                if wallet[1]==0 and wallet[0]>0:\n",
    "                    wallet[0] -= 3\n",
    "                else:\n",
    "                    return False\n",
    "            print(wallet)\n",
    "            if wallet[0] < 0 or wallet[1] < 0 or wallet[2] < 0:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lemonadeChange(self, bills: List[int]) -> bool:\n",
    "        a = [0,0,0]\n",
    "        for i in bills:\n",
    "            print(i,a)\n",
    "            if i==5:\n",
    "                a[0]+=1\n",
    "            elif i==10:\n",
    "                if a[0]==0:\n",
    "                    return False\n",
    "                else:\n",
    "                    a[0]-=1\n",
    "                    a[1]+=1\n",
    "            elif i==20:\n",
    "                if a[1]==0:\n",
    "                    if a[0]<3:\n",
    "                        return False\n",
    "                    else:\n",
    "                        a[0]-=3\n",
    "                else:\n",
    "                    if a[0]==0:\n",
    "                        return False\n",
    "                    else:\n",
    "                        a[0]-=1\n",
    "                        a[1]-=1\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lemonadeChange(self, bills: List[int]) -> bool:\n",
    "        change = [0, 0]\n",
    "        for i in range(len(bills)):\n",
    "            if bills[i] == 5:\n",
    "                change[0] += 1\n",
    "            if bills[i] == 10:\n",
    "                change[0] -= 1\n",
    "                change[1] += 1\n",
    "            if bills[i] == 20:\n",
    "                if change[1] < 1:\n",
    "                    change[0] -= 3\n",
    "                else:\n",
    "                    change[0] -= 1\n",
    "                    change[1] -= 1\n",
    "\n",
    "            print(change)\n",
    "            if change[0] < 0 or change[1] <0:\n",
    "                return False\n",
    "        \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lemonadeChange(self, bills: List[int]) -> bool:\n",
    "        five=0\n",
    "        ten=0\n",
    "        twenty=0\n",
    "        #bills.sort()\n",
    "        for val in bills:\n",
    "            print(five,ten,twenty)\n",
    "            if val==5:\n",
    "                five+=1\n",
    "            elif val==10:\n",
    "                if (five<=0):\n",
    "                    return False\n",
    "                else:\n",
    "                    five-=1\n",
    "                    ten+=1\n",
    "            else:\n",
    "                \n",
    "                if (ten>0) & (five>0):\n",
    "                    ten-=1\n",
    "                    five-=1\n",
    "                    twenty+=1\n",
    "                elif five>=3:\n",
    "                    five -=3\n",
    "                    twenty+=1\n",
    "                else:\n",
    "                    \n",
    "                    return False \n",
    "        return True\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lemonadeChange(self, bills: List[int]) -> bool:\n",
    "        five=0\n",
    "        ten=0\n",
    "        twenty=0\n",
    "        #bills.sort()\n",
    "        for val in bills:\n",
    "            print(five,ten,twenty)\n",
    "            if val==5:\n",
    "                five+=1\n",
    "            elif val==10:\n",
    "                if (five<=0):\n",
    "                    return False\n",
    "                else:\n",
    "                    five-=1\n",
    "                    ten+=1\n",
    "            else:\n",
    "                \n",
    "                if ten>0 and five>0:\n",
    "                    ten-=1\n",
    "                    five-=1\n",
    "                    twenty+=1\n",
    "                elif five>=3:\n",
    "                    five -=3\n",
    "                    twenty+=1\n",
    "                else:\n",
    "                    \n",
    "                    return False \n",
    "        return True\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lemonadeChange(self, bills: List[int]) -> bool:\n",
    "        five_list = []\n",
    "        ten_list = []\n",
    "\n",
    "        for bill in bills:\n",
    "            if bill == 5:\n",
    "                five_list.append(bill)\n",
    "            elif bill == 10:\n",
    "                if len(five_list):\n",
    "                    ten_list.append(bill)\n",
    "                    five_list.pop()\n",
    "                else:\n",
    "                    return False\n",
    "            elif bill == 20:\n",
    "                if len(ten_list) and len(five_list):\n",
    "                    ten_list.pop()\n",
    "                    five_list.pop()\n",
    "                else:\n",
    "                    if len(five_list) >= 3:\n",
    "                        for _ in range(3):\n",
    "                            five_list.pop()\n",
    "                    else:\n",
    "                        return False\n",
    "        \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lemonadeChange(self, bills: List[int]) -> bool:\n",
    "        five=0\n",
    "        ten=0\n",
    "        tw=0\n",
    "        for i in bills:\n",
    "            if i==5:\n",
    "                five+=1\n",
    "            if i==10:\n",
    "                if five<=0:\n",
    "                    return False\n",
    "                ten+=1\n",
    "                five-=1\n",
    "            if i==20:\n",
    "                if five>0 and ten>0:\n",
    "                    five-=1\n",
    "                    ten-=1\n",
    "                    tw+=1\n",
    "                elif five>=3:\n",
    "                    five-=3\n",
    "                    tw+=1\n",
    "                else:\n",
    "                    return False\n",
    "        return True\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lemonadeChange(self, bills: List[int]) -> bool:\n",
    "        five_dollar = []\n",
    "        ten_dollar = []\n",
    "        for i in bills:\n",
    "            if i == 5:\n",
    "                five_dollar.append(1)\n",
    "            if i == 10:\n",
    "                ten_dollar.append(1)\n",
    "                try:\n",
    "                    five_dollar.pop()\n",
    "                except IndexError:\n",
    "                    return False\n",
    "            if i == 20:\n",
    "                if ten_dollar and five_dollar:\n",
    "                    ten_dollar.pop()\n",
    "                    five_dollar.pop()\n",
    "                else:\n",
    "                    try:\n",
    "                        five_dollar.pop()\n",
    "                        five_dollar.pop()\n",
    "                        five_dollar.pop()\n",
    "                    except IndexError:\n",
    "                        return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lemonadeChange(self, bills: List[int]) -> bool:\n",
    "        five = ten = twenty = 0\n",
    "        for bill in bills:\n",
    "            if bill == 5:\n",
    "                five += 1\n",
    "            elif bill == 10:\n",
    "                ten += 1\n",
    "                if five > 0:\n",
    "                    five -= 1\n",
    "                else:\n",
    "                    return False\n",
    "            elif bill == 20:\n",
    "                twenty += 1\n",
    "                if ten > 0:\n",
    "                    ten -= 1\n",
    "                    if five > 0:\n",
    "                        five -= 1\n",
    "                    else:\n",
    "                        return False\n",
    "                else:\n",
    "                    if five >= 3:\n",
    "                        five -= 3\n",
    "                    else:\n",
    "                        return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lemonadeChange(self, bills: List[int]) -> bool:\n",
    "     five=0\n",
    "     ten = 0\n",
    "     for i in bills:\n",
    "        if i==5: five +=1\n",
    "        elif i==10:\n",
    "            ten +=1\n",
    "            five-=1\n",
    "        elif i==20:\n",
    "            if ten>0:\n",
    "                ten-=1;five -=1\n",
    "            else:five -=3\n",
    "        if five<0: return False\n",
    "     return True\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lemonadeChange(self, bills: List[int]) -> bool:\n",
    "        # 顾客可能付给你5、10、20美元，你要判断能否正确给顾客找零；\n",
    "        # 顾客支付的减去5的值，如果能在你的零钱包中找到，则可以正确找零；结果将是n个5和m个10的组合。\n",
    "\n",
    "        cashier_5 = []\n",
    "        cashier_10 = []\n",
    "        for bill in bills:\n",
    "            if bill == 5:\n",
    "                cashier_5.append(5)\n",
    "            if bill == 10:\n",
    "                if  cashier_5:\n",
    "                    cashier_5.pop() # 找5元\n",
    "                    cashier_10.append(10) # 将10放入\n",
    "                else:\n",
    "                    return False # 若没有零钱，返回false\n",
    "            if bill == 20:\n",
    "                if  cashier_10:\n",
    "                    cashier_10.pop() #优先找10元\n",
    "                    if  cashier_5:\n",
    "                        cashier_5.pop()#再找5元\n",
    "                    else:\n",
    "                        return False\n",
    "                else: # 如果10元为空\n",
    "                    if len(cashier_5) >= 3:\n",
    "                        cashier_5.pop()\n",
    "                        cashier_5.pop()\n",
    "                        cashier_5.pop()\n",
    "                    else:\n",
    "                        return False\n",
    "        return True\n",
    "                \n",
    "\n",
    "\n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def lemonadeChange(self, bills: List[int]) -> bool:\n",
    "\n",
    "        five = ten = 0\n",
    "\n",
    "        for b in bills:\n",
    "\n",
    "            if b == 5:  # 无需找零\n",
    "\n",
    "                five += 1\n",
    "\n",
    "            elif b == 10:  # 返还 5\n",
    "\n",
    "                five -= 1\n",
    "\n",
    "                ten += 1\n",
    "\n",
    "            elif ten:  # 此时 b=20，返还 10+5\n",
    "\n",
    "                five -= 1\n",
    "\n",
    "                ten -= 1\n",
    "\n",
    "            else:  # 此时 b=20，返还 5+5+5\n",
    "\n",
    "                five -= 3\n",
    "\n",
    "            if five < 0:  # 无法正确找零\n",
    "\n",
    "                return False\n",
    "\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lemonadeChange(self, bills: List[int]) -> bool:\n",
    "        five = 0\n",
    "        ten = 0\n",
    "        twenty = 0\n",
    "        \n",
    "        for bill in bills:\n",
    "            # 情况一：收到5美元\n",
    "            if bill == 5:\n",
    "                five += 1\n",
    "            \n",
    "            # 情况二：收到10美元\n",
    "            if bill == 10:\n",
    "                if five <= 0:\n",
    "                    return False\n",
    "                ten += 1\n",
    "                five -= 1\n",
    "            \n",
    "            # 情况三：收到20美元\n",
    "            if bill == 20:\n",
    "                # 先尝试使用10美元和5美元找零\n",
    "                if five > 0 and ten > 0:\n",
    "                    five -= 1\n",
    "                    ten -= 1\n",
    "                    #twenty += 1\n",
    "                # 如果无法使用10美元找零，则尝试使用三张5美元找零\n",
    "                elif five >= 3:\n",
    "                    five -= 3\n",
    "                    #twenty += 1\n",
    "                else:\n",
    "                    return False\n",
    "        \n",
    "        return True\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def lemonadeChange(self, bills: List[int]) -> bool:\n",
    "        # 初始化钞票字典，初始数量为0\n",
    "        bills_dict = defaultdict(int)\n",
    "        \n",
    "        for bill in bills:\n",
    "            # 情况一：收到5美元\n",
    "            if bill == 5:\n",
    "                bills_dict[5] += 1\n",
    "            \n",
    "            # 情况二：收到10美元\n",
    "            if bill == 10:\n",
    "                if bills_dict[5] <= 0:\n",
    "                    return False\n",
    "                bills_dict[10] += 1\n",
    "                bills_dict[5] -= 1\n",
    "            \n",
    "            # 情况三：收到20美元\n",
    "            if bill == 20:\n",
    "                # 先尝试使用10美元和5美元找零\n",
    "                if bills_dict[5] > 0 and bills_dict[10] > 0:\n",
    "                    bills_dict[5] -= 1\n",
    "                    bills_dict[10] -= 1\n",
    "                # 如果无法使用10美元找零，则尝试使用三张5美元找零\n",
    "                elif bills_dict[5] >= 3:\n",
    "                    bills_dict[5] -= 3\n",
    "                else:\n",
    "                    return False\n",
    "        \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lemonadeChange(self, bills: List[int]) -> bool:\n",
    "        five=ten=0\n",
    "        for i in bills:\n",
    "            if i==5:\n",
    "                five+=1\n",
    "            elif i==10:\n",
    "                ten+=1\n",
    "                five-=1\n",
    "            elif ten:\n",
    "                five-=1\n",
    "                ten-=1\n",
    "            else:\n",
    "                five-=3\n",
    "            if five<0:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lemonadeChange(self, bills: List[int]) -> bool:\n",
    "        numof5,numof10=0,0\n",
    "        for bill in bills:\n",
    "            if bill==5:\n",
    "                numof5+=1\n",
    "            if bill==10:\n",
    "                if numof5:\n",
    "                    numof5-=1\n",
    "                    numof10+=1\n",
    "                else:\n",
    "                    return False\n",
    "            if bill==20:\n",
    "                if numof10 and numof5:\n",
    "                    numof10-=1\n",
    "                    numof5-=1\n",
    "                elif numof5>=3:\n",
    "                    numof5-=3\n",
    "                else:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lemonadeChange(self, bills: List[int]) -> bool:\n",
    "        five = ten = 0\n",
    "        for b in bills:\n",
    "            if b == 5:  # 无需找零\n",
    "                five += 1\n",
    "            elif b == 10:  # 返还 5\n",
    "                five -= 1\n",
    "                ten += 1\n",
    "            elif ten:  # 此时 b=20，返还 10+5\n",
    "                five -= 1\n",
    "                ten -= 1\n",
    "            else:  # 此时 b=20，返还 5+5+5\n",
    "                five -= 3\n",
    "            if five < 0:  # 无法正确找零\n",
    "                return False\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lemonadeChange(self, bills: List[int]) -> bool:\n",
    "        s5, s10 = 0, 0\n",
    "        for i in bills:\n",
    "            if i == 5:\n",
    "                s5 += 1\n",
    "            elif i == 10:\n",
    "                if s5 == 0:\n",
    "                    return False\n",
    "                s5 -=1\n",
    "                s10 += 1\n",
    "            else:\n",
    "                if s5 > 0 and s10 > 0:\n",
    "                    s5 -= 1\n",
    "                    s10 -= 1\n",
    "                elif s5 > 2:\n",
    "                    s5 -= 3\n",
    "                else:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lemonadeChange(self, bills: List[int]) -> bool:\n",
    "        our = []\n",
    "        for value in bills:\n",
    "            if value == 5:\n",
    "                our.append(5)\n",
    "            elif value == 10:\n",
    "                if 5 in our:\n",
    "                    our.remove(5)\n",
    "                    our.append(10)\n",
    "                else:\n",
    "                    return False\n",
    "            else:\n",
    "                if 10 in our and 5 in our:\n",
    "                    our.remove(5)\n",
    "                    our.remove(10)\n",
    "                else:\n",
    "                    try:\n",
    "                        our.remove(5)\n",
    "                        our.remove(5)\n",
    "                        our.remove(5)\n",
    "                    except Exception as e:\n",
    "                        return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lemonadeChange(self, bills: List[int]) -> bool:\n",
    "        numcash = [0] * 3 # hash table: 0, 5, 10\n",
    "        for bill in bills:\n",
    "            if bill == 5:\n",
    "                numcash[0] += 1\n",
    "                continue\n",
    "            elif bill == 10:\n",
    "                if numcash[0] >= 1:\n",
    "                    numcash[0] -= 1\n",
    "                    numcash[1] += 1\n",
    "                    continue\n",
    "                else:\n",
    "                    return False\n",
    "            else: # 20\n",
    "                if numcash[0] >= 1 and numcash[1] >= 1:\n",
    "                    numcash[0] -= 1\n",
    "                    numcash[1] -= 1\n",
    "                    numcash[2] += 1\n",
    "                    continue\n",
    "                if numcash[0] >= 3:\n",
    "                    numcash[0] -= 3\n",
    "                    numcash[2] += 1\n",
    "                    continue\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lemonadeChange(self, bills: List[int]) -> bool:\n",
    "        stack = {'five': 0, 'ten': 0, \"twenty\": 0}\n",
    "        while bills:\n",
    "            temp = bills.pop(0)\n",
    "            if temp == 5:\n",
    "                stack['five'] += 1\n",
    "            elif temp == 10:\n",
    "                stack['five'] -= 1\n",
    "                stack['ten'] += 1\n",
    "            elif temp == 20 and stack['ten'] > 0:\n",
    "                stack['five'] -= 1\n",
    "                stack['ten'] -= 1\n",
    "                stack['twenty'] -= 1\n",
    "            else:\n",
    "                stack['five'] -= 3\n",
    "                stack['twenty'] -= 1\n",
    "            if stack['five'] < 0:\n",
    "                return False\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lemonadeChange(self, bills: List[int]) -> bool:\n",
    "        five = ten = 0\n",
    "        for b in bills:\n",
    "            if b == 5:  \n",
    "                five += 1\n",
    "            elif b == 10:  \n",
    "                five -= 1\n",
    "                ten += 1\n",
    "            elif b == 20:\n",
    "                if ten > 0:  \n",
    "                    five -= 1\n",
    "                    ten -= 1\n",
    "                else: \n",
    "                    five -= 3\n",
    "            if five < 0:  \n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lemonadeChange(self, bills: List[int]) -> bool:\n",
    "        #贪心算法局部最优解\n",
    "        five=ten=0\n",
    "        for i in bills:\n",
    "            if i==5:\n",
    "                five+=1\n",
    "            elif i==10:\n",
    "                five-=1\n",
    "                ten+=1\n",
    "            else:\n",
    "                if ten:\n",
    "                    ten-=1\n",
    "                    five-=1\n",
    "                else:\n",
    "                    five-=3\n",
    "            if five<0:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lemonadeChange(self, bills: List[int]) -> bool:\n",
    "        five = ten = 0\n",
    "        for b in bills:\n",
    "            if b == 5:  # 无需找零\n",
    "                five += 1\n",
    "            elif b == 10:  # 返还 5\n",
    "                five -= 1\n",
    "                ten += 1\n",
    "            elif ten:  # 此时 b=20，返还 10+5\n",
    "                five -= 1\n",
    "                ten -= 1\n",
    "            else:  # 此时 b=20，返还 5+5+5\n",
    "                five -= 3\n",
    "            if five < 0:  # 无法正确找零\n",
    "                return False\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lemonadeChange(self, bills: List[int]) -> bool:\n",
    "        five = 0\n",
    "        ten = 0\n",
    "        for i in range(len(bills)):\n",
    "            if bills[i]==5:\n",
    "                five +=1\n",
    "            if bills[i] == 10:\n",
    "                if five <1:\n",
    "                    return False\n",
    "                else:\n",
    "                    five -=1\n",
    "                    ten +=1\n",
    "            if bills[i] == 20:\n",
    "                if ten <1:\n",
    "                    if five<3:\n",
    "                        return False\n",
    "                    else:\n",
    "                        five -=3\n",
    "                else:\n",
    "                    if five<1:\n",
    "                        return False\n",
    "                    else:\n",
    "                        five-=1\n",
    "                        ten-=1\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lemonadeChange(self, bills: List[int]) -> bool:\n",
    "        # 当前手中的5美元个数\n",
    "        cur_5 = 0\n",
    "        cur_10 = 0\n",
    "        for i in bills:\n",
    "            if i == 5:\n",
    "                cur_5 += 1\n",
    "            elif i == 10:\n",
    "                cur_10 += 1\n",
    "                cur_5 -= 1\n",
    "            else:\n",
    "                if cur_10 > 0:\n",
    "                    cur_10 -= 1\n",
    "                    cur_5 -= 1\n",
    "                else:\n",
    "                    cur_5 -= 3\n",
    "            if cur_5 < 0:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lemonadeChange(self, bills: List[int]) -> bool:\n",
    "        checks = [0,0]\n",
    "        for i in bills:\n",
    "            if i == 5:\n",
    "                checks[0]+=1\n",
    "            if i == 10:\n",
    "                checks[1]+=1\n",
    "                checks[0]-=1\n",
    "            if i == 20:\n",
    "                if checks[1]<=0:\n",
    "                    checks[0]-=3\n",
    "                else:\n",
    "                    checks[1]-=1\n",
    "                    checks[0]-=1\n",
    "            if checks[0]<0 or checks[1]<0:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lemonadeChange(self, bills: List[int]) -> bool:\n",
    "        five, ten = 0, 0\n",
    "        for i in range(len(bills)):\n",
    "            if bills[i] == 5:\n",
    "                five += 1\n",
    "            elif bills[i] == 10:\n",
    "                five -= 1\n",
    "                ten += 1\n",
    "            elif bills[i] == 20:\n",
    "                if ten > 0:\n",
    "                    five -= 1\n",
    "                    ten -= 1\n",
    "                else:\n",
    "                    five -= 3\n",
    "            if five < 0:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lemonadeChange(self, bills: List[int]) -> bool:\n",
    "        five = 0\n",
    "        ten = 0\n",
    "        twenty = 0\n",
    "        for i in range(len(bills)):\n",
    "            if bills[i]==5:\n",
    "                five+=1\n",
    "            if bills[i]==10:\n",
    "                if five==0:\n",
    "                    return False\n",
    "                five-=1\n",
    "                ten+=1\n",
    "            if bills[i]==20:\n",
    "                if five >0 and ten>0:\n",
    "                    five-=1\n",
    "                    ten-=1\n",
    "                elif five>=3:\n",
    "                    five-=3\n",
    "                else:\n",
    "                    return False\n",
    "        return True\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lemonadeChange(self, bills: List[int]) -> bool:\n",
    "        numcash = [0] * 2 # hash table: 5, 10\n",
    "        for bill in bills:\n",
    "            if bill == 5:\n",
    "                numcash[0] += 1\n",
    "                continue\n",
    "            elif bill == 10:\n",
    "                if numcash[0] >= 1:\n",
    "                    numcash[0] -= 1\n",
    "                    numcash[1] += 1\n",
    "                    continue\n",
    "                else:\n",
    "                    return False\n",
    "            else: # 20\n",
    "                if numcash[0] >= 1 and numcash[1] >= 1:\n",
    "                    numcash[0] -= 1\n",
    "                    numcash[1] -= 1\n",
    "                    continue\n",
    "                if numcash[0] >= 3:\n",
    "                    numcash[0] -= 3\n",
    "                    continue\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lemonadeChange(self, bills: List[int]) -> bool:\n",
    "        numFive = 0\n",
    "        numTen = 0\n",
    "        for i in range(0, len(bills)):\n",
    "            if bills[i] == 5:\n",
    "                numFive += 1\n",
    "            elif bills[i] == 10:\n",
    "                if numFive == 0:\n",
    "                    return False\n",
    "                else:\n",
    "                    numFive -= 1\n",
    "                    numTen += 1\n",
    "            else:\n",
    "                if numTen >= 1 and numFive >= 1:\n",
    "                    numTen -= 1\n",
    "                    numFive -= 1\n",
    "                    continue\n",
    "                elif numFive >= 3:\n",
    "                    numFive -= 3\n",
    "                    continue\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lemonadeChange(self, bills: List[int]) -> bool:\n",
    "        # 只需要维护三种金额的数量，5，10和20。\n",
    "        # 有如下三种情况：\n",
    "        #     情况一：账单是5，直接收下。\n",
    "        #     情况二：账单是10，消耗一个5，增加一个10\n",
    "        #     情况三：账单是20，优先消耗一个10和一个5，如果不够，再消耗三个5\n",
    "        five = ten = twenty = 0\n",
    "        for bill in bills:\n",
    "            if bill == 5:\n",
    "                five += 1\n",
    "            elif bill == 10:\n",
    "                if five <= 0:\n",
    "                    return False\n",
    "                ten += 1\n",
    "                five -= 1\n",
    "            else:\n",
    "                if ten > 0 and five >0:\n",
    "                    five -=1\n",
    "                    ten -= 1\n",
    "                    twenty += 1\n",
    "                elif five >=3:\n",
    "                    five -= 3\n",
    "                else:\n",
    "                    return False\n",
    "                \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lemonadeChange(self, bills: List[int]) -> bool:\n",
    "        fives=0\n",
    "        tens=0\n",
    "        for i in range(len(bills)):\n",
    "            if bills[i]==5:\n",
    "                fives+=1\n",
    "            elif bills[i]==10:\n",
    "                fives-=1\n",
    "                tens+=1\n",
    "                if fives<0:\n",
    "                    return False\n",
    "            elif bills[i]==20:\n",
    "                if tens>0 and fives>0:\n",
    "                    tens-=1\n",
    "                    fives-=1\n",
    "                elif fives>2:\n",
    "                    fives-=3\n",
    "                else:\n",
    "                    return False\n",
    "        return True\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lemonadeChange(self, bills: List[int]) -> bool:\n",
    "        # 只需要维护三种金额的数量，5，10和20。\n",
    "        # 有如下三种情况：\n",
    "        #     情况一：账单是5，直接收下。\n",
    "        #     情况二：账单是10，消耗一个5，增加一个10\n",
    "        #     情况三：账单是20，优先消耗一个10和一个5，如果不够，再消耗三个5\n",
    "        five = ten = twenty = 0\n",
    "        for bill in bills:\n",
    "            if bill == 5:\n",
    "                five += 1\n",
    "            if bill == 10:\n",
    "                if five <= 0:\n",
    "                    return False\n",
    "                ten += 1\n",
    "                five -= 1\n",
    "            if bill == 20:\n",
    "                if ten > 0 and five >0:\n",
    "                    five -=1\n",
    "                    ten -= 1\n",
    "                    twenty += 1\n",
    "                elif five >=3:\n",
    "                    five -= 3\n",
    "                else:\n",
    "                    return False\n",
    "                \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lemonadeChange(self, bills: List[int]) -> bool:\n",
    "        rest = {'5':0, '10':0, '20':0}\n",
    "        for i in range(len(bills)):\n",
    "            if bills[i] == 10:\n",
    "                if rest['5']<1:\n",
    "                    return False\n",
    "                else:\n",
    "                    rest['5'] -= 1\n",
    "            elif bills[i] == 20:\n",
    "                if rest['10']>=1 and rest['5']>=1:\n",
    "                    rest['5'] -= 1\n",
    "                    rest['10'] -= 1\n",
    "                elif rest['10']<1 and rest['5']>=3:\n",
    "                    rest['5'] -= 3\n",
    "                else:\n",
    "                    return False\n",
    "            rest[str(bills[i])] += 1\n",
    "        \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lemonadeChange(self, bills: List[int]) -> bool:\n",
    "        nums_five = 0\n",
    "        nums_ten = 0\n",
    "        for i in bills:\n",
    "            if i == 5:\n",
    "                nums_five += 1\n",
    "            elif i == 10:\n",
    "                nums_ten += 1\n",
    "                nums_five -= 1\n",
    "            elif i == 20 and nums_ten > 0:\n",
    "                nums_ten -= 1\n",
    "                nums_five -= 1\n",
    "            else:\n",
    "                nums_five -= 3\n",
    "            if nums_five < 0:\n",
    "                return False\n",
    "        return True"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
